﻿#pragma once
#include "Index.h"

/**
 * 二维区域和检索-矩阵不可变
 * 题目:https://leetcode.cn/problems/range-sum-query-2d-immutable/
 * 题解:https://leetcode.cn/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-he-jian-suo-ju-zhen-bu-ke-b-2z5n/
 * 数组 矩阵 前缀和
 *
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 * 计算其子矩形范围内元素的总和，该子矩阵的 左上角为(row1, col1) ，右下角为(row2, col2) 。
 * 实现 NumMatrix 类：
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和 。
 */
class NumMatrix
{
public:
    NumMatrix() = default;
    NumMatrix(std::vector<std::vector<int>>& matrix)
	{
        initRegion(matrix);
    }

    void initRegion(std::vector<std::vector<int>>& matrix)
    {
        _preSumMat.clear();
        //矩阵不为空
        _rowCount = matrix.size();
        _colCount= _rowCount> 0 ? matrix.front().size() : 0;
        if (_rowCount == 0 || _colCount == 0)
            return;
        //分配预计算矩阵内存
        _preSumMat.resize(_rowCount, std::vector<int>(_colCount, 0));

        //计算前缀和矩阵
        for(int row=0;row<_rowCount;++row)
        {
	        for(int col=0;col<_colCount;++col)
	        {
                _preSumMat[row][col] = matrix[row][col]
                    + regionSumSinceOrigin(row - 1, col) + regionSumSinceOrigin(row, col - 1) - regionSumSinceOrigin(row - 1, col - 1);
	        }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2)
	{
        return regionSumSinceOrigin(row2, col2) - regionSumSinceOrigin(row1 - 1, col2)
            - regionSumSinceOrigin(row2, col1 - 1) + regionSumSinceOrigin(row1 - 1, col1 - 1);
    }
private:
	int regionSumSinceOrigin(int row,int col)
	{
        if (row < 0 || row >= _rowCount || col < 0 || col >= _colCount)
            return 0;
        return _preSumMat[row][col];
	}
private:
    int _rowCount, _colCount;
    std::vector<std::vector<int>> _preSumMat;
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(NumMatrixTest, sumRegion)
{
    NumMatrix solution;

    std::vector<std::vector<int>> matrix;
    constexpr int row = 50;
    constexpr int col = 40;
    constexpr int minVal = -1000;
    constexpr int maxVal = 1000;
    constexpr int sumTimes = 1000;

    //随机构建矩阵内容
    matrix.resize(row, std::vector<int>(col, 0));
    for (int i = 0; i < row; ++i)
        for (int j = 0; j < col; ++j)
            matrix[i][j] = TestingUtil::randIntBetween(minVal, maxVal);
    solution.initRegion(matrix);

    //多次进行矩阵区域求和
    for(int testTime=0;testTime<sumTimes;++testTime)
    {
        //要进行求和的矩阵区域
        std::pair<int, int> regionStart =
            std::make_pair(TestingUtil::randIndexInSize(row), TestingUtil::randIndexInSize(col));
        std::pair<int, int> regionEnd =
            std::make_pair(regionStart.first + TestingUtil::randIndexInSize(row - regionStart.first - 1),
                regionStart.second + TestingUtil::randIndexInSize(col - regionStart.second - 1));

        //暴力法算出矩阵区域的和
        int expectSum = 0;
        for (int i = regionStart.first; i <= regionEnd.first; ++i)
            for (int j = regionStart.second; j <= regionEnd.second; ++j)
                expectSum += matrix[i][j];

        //solution算出矩阵居于的和
        const int resultSum = solution.sumRegion(regionStart.first, regionStart.second, regionEnd.first, regionEnd.second);

        //断言相等
        ASSERT_EQ(resultSum, expectSum)
            << "matrix=" << FormatedUtil::dumpFormated(matrix) << std::endl
            << "region_start=(" << regionStart.first << "," << regionStart.second <<")"<< std::endl
            << "region_end=(" << regionEnd.first << "," << regionEnd.second <<")" <<std::endl;
    }
}
#endif